package com.example.linked.skiplist;

import java.util.Random;

public class Skiplist {
    final int HEAD_VALUE = -1; // 链表头节点的值

    private Node head;

    // 跳表层级数
    private int levels;
    // 跳表节点数(不包括索引层)
    int size;

    public Skiplist() {
        // 对跳表进行初始化，此时跳表中只有一个头结点,层级也只有一级
        head = new Node(HEAD_VALUE);
        this.levels = 1;
        this.size = 0;
    }

    /**
     * 向跳表添加一个数据(不考虑添加索引层)
     * 1.遍历跳表，找到合适的插入位置（原链表中 >= num 的最小节点前）
     * 逐层遍历链表，如果在某层遇到了大于num的节点，则说明找到了位置
     * <p>
     * 2.将节点插入
     * <p>
     * 3.根据扔硬币决定（是否）生成索引
     * 索引是从下往上生成，
     * 从下往上生成索引的过程中，一旦有一层不生成索引后，至此以上的所有层均不能再生成索引
     * 并且每层开始向下层跳转的那个节点就是该层可能要生成索引的前一个节点！！！
     *
     * @param num
     */
    public void add(int num) {
        Node cur = head;
        // 声明一个数组，用于存放每层要生成索引的节点,最后一个元素是要插入的原始链表位置的前一个节点
        Node[] nodes = new Node[levels];
        // 1. 遍历跳表，找到合适的插入位置
        // 外层循环控制层级的切换，内存循环控制每层的遍历
        // levelIndex代表索引层数
        int levelIndex = 0;
        while (cur != null) {
            // 同一层级，cur的右节点值小于target时依次向右移动cur指针
            while (cur.right != null && cur.right.val < num) {
                cur = cur.right;
            }
            // 退出内层循环说明cur右节点值大于或者等于num,右侧为结尾 or 右侧值大 or 右侧值相同
            // 在要跳到下层链表前将该节点存入索引节点数组中
            // 因为每层向下跳转的地方就是可能要生成索引的地方
            nodes[levelIndex++] = cur;
            // 跳到下一层去,继续查找下一层的位置
            cur = cur.down;
        }
        // 退出双重循环时，一定是移动到了原链表层的合适位置，
        // 且cur一定是指向要插入位置的前一个节点

        // 2. 将数据插入原链表层的链表中
        Node tmp = nodes[--levelIndex];
        Node newNode = new Node(num, tmp.right, null);
        tmp.right = newNode;
        size++;

        // 3.根据扔硬币决定（是否）生成索引
        addIndicesByCoinFlip(newNode, nodes, levelIndex);

    }

    /**
     * 删除指定的节点
     * 逐层遍历链表，如果在某层遇到了等于target的节点，则开始从上往下逐层删除
     * 逐层遍历的过程和查找是否存在某个元素的是一样的，可以将整个查找过程单独写成一个方法
     *
     * @param num
     * @return
     */
    public boolean erase(int num) {
        boolean flag = false;
        Node preNode = findNode(num, head);
        // 返回值不为null说明跳表中存在该元素，下面进行逐层删除动作
        while (preNode != null) {
            Node right = preNode.right; // 要删除的目标节点
            // 删除该层的节点
            preNode.right = right.right;
            right.right = null;
            flag = true;
            preNode = findNode(num, preNode.down);
        }
        if (flag) {
            size--;
        }
        return flag;
    }

    /**
     * 查询跳表中是否有目标值
     * <p>
     * 逐层遍历链表，如果在某层遇到了等于target的节点，则说明存在
     * 逐层遍历的过程和删除的是一样的，可以将整个查找过程单独写成一个方法
     *
     * @param target
     * @return
     */
    public boolean search(int target) {
        return findNode(target, head) != null;
    }

    /**
     * 从指定节点开始逐层遍历链表，如果某个节点的右节点值等于tartget,则返回该元素
     *
     * @param target
     * @return
     */
    private Node findNode(int target, Node startNode) {
        Node cur = startNode;
        // 外层循环控制层级的切换，内存循环控制每层的遍历
        while (cur != null) {
            // 同一层级，cur的右节点值小于target时依次向右移动cur指针
            while (cur.right != null && cur.right.val < target) {
                cur = cur.right;
            }
            // 退出内层循环说明cur右节点值大于或者等于target
            Node targetNode = cur.right;

            // 下一个元素的值和target相同的元素,返回将该元素即可
            if (targetNode != null && targetNode.val == target) {
                return cur;
            }
            // 大于的情况则需要移动到下一层，然后继续
            cur = cur.down;
        }
        // 从指定节点开始遍历完了整个跳表，说明没有该元素,返回空
        return null;
    }

    /**
     * 抛硬币的方式决定是否给新节点建立索引。
     * 索引层级可能超出现有跳表的层数，再抛一次决定是否生成索引。
     * 索引的层级应该由原始链表的数量来决定，不应该简单的在原有层级数上随机是否+1
     * 抛硬币，为1并且 层级数(levels) < 原始链表长度/64 (64是个实验值) 就在该层添加索引
     *
     * @param target  要生成索引的节点
     * @param nodes   可能在这些节点后添加新索引节点
     * @param indices 当前索引层数
     */
    private void addIndicesByCoinFlip(Node target, Node[] nodes, int indices) {
        Node downNode = target;
        Random random = new Random();
        while (random.nextInt(2) == 1 && levels < (size >> 6)) {
            // 在原来的层级从下往上加索引
            if (indices > 0) {
                Node prev = nodes[--indices];
                Node newIndex = new Node(target.val, prev.right, downNode);
                prev.right = newIndex;
                downNode = newIndex;
            } else {
                // 新建索引节点和head 节点
                Node newIndex = new Node(target.val, null, downNode);
                Node newHead = new Node(HEAD_VALUE, newIndex, head);
                head = newHead; // head 指针上移
                levels++; // 跳表层数加 1
            }
        }

    }
}
